#define DEBUG
#include <cstdio>

using namespace std;

const int maxn=10000, maxm=10000, inf=0x7ffffff;

int min(int a, int b) {
  return a<b ? a : b;
}

int getFa(int *set, int o) {
  return set[o]==o ? o : (set[o]=getFa(set, set[o]));
}

int solve(int o, int n, int m, int k, int side[][3]) {
  static bool book[maxm+1];
  static int set[maxn+1];
  int ret=inf;
  if (o<=m) {
    ret = min(ret, solve(o+1, n, m, k, side));
    book[o] = true;
    ret = min(ret, solve(o+1, n, m, k, side));
    book[o] = false;
  } else {
    for (int i=1; i<=n; i++) {
      set[i] = i;
    }
    ret = 0;
    for (int i=1; i<=m; i++) {
      int x, y;
      if (book[i] && (x=getFa(set, side[i][1]))!=(y=getFa(set, side[i][2]))) {
	set[y] = x;
	ret += side[i][0];
      }
    }
    for (int i=1; i<=k; i++) {
      if (getFa(set, i)!=getFa(set, n-i+1)) {
	return inf;
      }
    }
  }
  return ret;
}

int main() {
#ifdef DEBUG
  freopen("0.in", "r", stdin);
  freopen("0.out", "w", stdout);
#endif

  static int side[maxm+1][3];
  int n, m, k;
  scanf("%d %d %d", &n, &m, &k);
  for (int i=1; i<=m; i++) {
    scanf("%d %d %d", side[i]+1, side[i]+2, side[i]);
  }
  int t=solve(1, n, m, k, side);
  printf(t<inf ? "%d" : "-1", t);

  fclose(stdin);
  fclose(stdout);
  return 0;
}
